1. Technical Field of the Invention
The invention relates to methods, apparatus, and signals used in channel coding and decoding, and, in particular embodiments to methods, apparatus and signals for use with turbo and turbo-trellis encoding and decoding for communication channels.
2. Description of Related Art
A significant amount of interest has recently been paid to channel coding. For example a recent authoritative text states:
“Channel coding refers to the class of signal transformations designed to improve communications performance by enabling the transmitted signals to better withstand the effects of various channel impairments, such as noise, interference, and fading. These signal-processing techniques can be thought of as vehicles for accomplishing desirable system trade-offs (e.g., error-performance versus bandwidth, power versus bandwidth). Why do you suppose channel coding has become such a popular way to bring about these beneficial effects? The use of large-scale integrated circuits (LSI) and high-speed digital signal processing (DSP) techniques have made it possible to provide as much as 10 dB performance improvement through these methods, at much less cost than through the use of most other methods such as higher power transmitters or larger antennas.”
From “Digital Communications” Fundamentals and Applications Second Edition by Bernard Sklar, page 305 © 2001 Prentice Hall PTR.
Stated differently, improved coding techniques may provide systems that can operate at lower power or may be used to provide higher data rates.
Conventions and Definitions:
Particular aspects of the invention disclosed herein depend upon and are sensitive to the sequence and ordering of data. To improve the clarity of this disclosure the following convention is adopted. Usually, items are listed in the order that they appear. Items listed as #1, #2, #3 are expected to appear in the order #1, #2, #3 listed, in agreement with the way they are read, i.e. from left to right. However, in engineering drawings, it is common to show a sequence being presented to a block of circuitry, with the right most tuple representing the earliest sequence, as shown in FIG. 2, where 207 is the earliest tuple, followed by tuple 209. The IEEE Standard Dictionary of Electrical and Electronics Terms, Sixth Edition, defines tuple as a suffix meaning an ordered set of terms (sequence) as in N-tuple. A tuple as used herein is merely a grouping of bits having a relationship to each other.
Herein, the convention is adopted that items, such as tuples will be written in the same convention as the drawings. That is in the order that they sequentially proceed in a circuit. For example, “Tuples 207 and 209 are accepted by block 109” means tuple 207 is accepted first and then 209 is accepted, as is seen in FIG. 2. In other words the text will reflect the sequence implied by the drawings. Therefore a description of FIG. 2 would say “tuples 207 and 209 are provided to block 109” meaning that tuple 207 is provided to block 109 before tuple 209 is provided to block 109.
Herein an interleaver is defined as a device having an input and an output. The input accepting data tuples and the output providing data tuples having the same component bits as the input tuples, except for order.
An integral tuple (IT) interleaver is defined as an interleaver that reorders tuples that have been presented at the input, but does not separate the component bits of the input tuples. That is the tuples remain as integral units and adjacent bits in an input tuple will remain adjacent, even though the tuple has been relocated. The tuples, which are output from an IT interleaver are the same as the tuples input to interleaver, except for order. Hereinafter when the term interleaver is used, an IT interleaver will be meant.
A separable tuple (ST) interleaver is defined as an interleaver that reorders the tuples input to it in the same manner as an IT interleaver, except that the bits in the input tuples are interleaved independently, so that bits that are adjacent to each other in an input tuple are interleaved separately and are interleaved into different output tuples. Each bit of an input tuple, when interleaved in an ST interleaver, will typically be found in a different tuple than the other bits of the input tuple from where it came. Although the input bits are interleaved separately in an ST interleaver, they are generally interleaved into the same position within the output tuple as they occupied within the input tuple. So for example, if an input tuple comprising two bits, a most significant bit and a least significant bit, is input into an ST interleaver the most significant bit will be interleaved into the most significant bit position in a first output tuple and the least significant bit will be interleaved into the least significant bit position in a second output tuple.
Modulo-N sequence designation is a term meaning the modulo-N of the position of an element in a sequence. If there are k item s(1) in a sequence then the items have ordinal numbers 0 to k−1, i.e. I0 through I(k−1) representing the position of each time in the sequence. The first item in the sequence occupies position 0, the second item in a sequence I1 occupies position 1, the third item in the sequence I2 occupies position 2 and so forth up to item Ik−1, which occupies the k′th or last position in the sequence. The modulo-N sequence designation is equal to the position of the item in the sequence modulo-N . For example, the modulo-2 sequence designation of I0=0, the modulo-2 sequence designation of I1=1, and the modulo-2 sequence designation of I2=0 and so forth.
A modulo-N interleaver is defined as an interleaver wherein the interleaving function depends on the modulo-N value of the tuple input to the interleaver. Modulo interleavers are further defined and illustrated herein.
A modulo-N encoding system is one that employs one or more modulo interleavers.